//
//  ACLFUCache.m
//  Cache
//
//  Created by caixiang on 2021/8/14.
//

#import "ACLFUCache.h"
#import <pthread.h>
#import <UIKit/UIKit.h>
#import "ACDoubleLinkedList.h"
#import "ACLinkedNode.h"

@interface ACLFUCache() {
    pthread_mutex_t _lock;
    NSUInteger _totalCount;
    NSUInteger _totalCost;
    // key 和 node 的 map
    CFMutableDictionaryRef _map;
    // freq 和 doubleLinkedList 的 map
    CFMutableDictionaryRef _freqMap;
    NSUInteger _minFreq;
}
@end

@implementation ACLFUCache

- (instancetype)init {
    self = [super init];
    if (self) {
        self.countLimit = NSUIntegerMax;
        self.costLimit = NSUIntegerMax;
        [self setup];
    }
    return self;
}

- (void)setup {
    pthread_mutex_init(&_lock, NULL);
    _minFreq = 1;
    _map = CFDictionaryCreateMutable(CFAllocatorGetDefault(), 0, &kCFTypeDictionaryKeyCallBacks, &kCFTypeDictionaryValueCallBacks);
    _freqMap = CFDictionaryCreateMutable(CFAllocatorGetDefault(), 0, &kCFTypeDictionaryKeyCallBacks, &kCFTypeDictionaryValueCallBacks);
    self.shouldRemoveAllObjectsWhenEnteringBackground = YES;
    self.shouldRemoveAllObjectsOnMemoryWarning = YES;
    [[NSNotificationCenter defaultCenter] addObserver:self selector:@selector(_appDidReceiveMemoryWarningNotification) name:UIApplicationDidReceiveMemoryWarningNotification object:nil];
    [[NSNotificationCenter defaultCenter] addObserver:self selector:@selector(_appDidEnterBackgroundNotification) name:UIApplicationDidEnterBackgroundNotification object:nil];
}

#pragma mark - notification
- (void)_appDidReceiveMemoryWarningNotification {
    if (self.didReceiveMemoryWarningBlock) {
        self.didReceiveMemoryWarningBlock(self);
    }
    if (self.shouldRemoveAllObjectsOnMemoryWarning) {
        [self removeAllObjects];
    }
}

- (void)_appDidEnterBackgroundNotification {
    if (self.didEnterBackgroundBlock) {
        self.didEnterBackgroundBlock(self);
    }
    if (self.shouldRemoveAllObjectsWhenEnteringBackground) {
        [self removeAllObjects];
    }
}

#pragma mark - public
- (instancetype)initWithCapacity:(NSUInteger)capacity {
    self = [super init];
    if (self) {
        self.countLimit = capacity;
        self.costLimit = NSUIntegerMax;
        [self setup];
    }
    return self;
}

- (BOOL)containsObjectForKey:(id)key {
    if (!key) return NO;
    pthread_mutex_lock(&_lock);
    BOOL contains = CFDictionaryContainsKey(_map, (__bridge const void *)(key));
    pthread_mutex_unlock(&_lock);
    return contains;
}

- (nullable id)objectForKey:(id)key {
    if (!key) return nil;
    pthread_mutex_lock(&_lock);
    ACLinkedNode *node = CFDictionaryGetValue(_map, (__bridge const void *)(key));
    if (node) {
        //增加数据的访问频率
        [self freqPlus:node];
    }
    pthread_mutex_unlock(&_lock);
    return node?node.value:nil;
}

- (void)setObject:(nullable id)object forKey:(id)key {
    [self setObject:object forKey:key cost:0];
}

- (void)setObject:(nullable id)object forKey:(nonnull id)key cost:(NSUInteger)cost {
    if (!key) return;
    if (_countLimit <= 0) return;
    if (!object) {
        [self removeObjectForKey:key];
        return;
    }
    pthread_mutex_lock(&_lock);
    ACLinkedNode *node = CFDictionaryGetValue(_map, (__bridge const void *)(key));
    if (node != nil) {
        _totalCost -= node.cost;
        _totalCost += node.cost;
        node.cost = cost;
        node.value = object;
        //增加数据的访问频率
        [self freqPlus:node];
    } else{
        //淘汰数据(需要把即将加入的数据 cost 提前计算)
        [self eliminate:cost];
        //限制大小
        if (cost <= _costLimit) {
            ACLinkedNode *newNode = [[ACLinkedNode alloc] initWithKey:key value:object frequency:1];
            newNode.cost = cost;
            NSNumber *minFreq = @1;
            CFDictionarySetValue(_map, (__bridge const void *)(key), (__bridge const void *)(newNode));
            ACDoubleLinkedList *linkList = CFDictionaryGetValue(_freqMap, (__bridge const void *)(minFreq));
            if (linkList == nil) {
                linkList = [[ACDoubleLinkedList alloc] init];
                CFDictionarySetValue(_freqMap, (__bridge const void *)(minFreq), (__bridge const void *)(linkList));
            }
            [linkList insertNodeAtHead:newNode];
            _minFreq = 1;
            _totalCount ++;
            _totalCost += cost;
        } else{
            NSLog(@"cost = %zd 超出限制 costLimit = %zd",cost,_costLimit);
        }
    }
    pthread_mutex_unlock(&_lock);
}

- (void)removeObjectForKey:(id)key {
    if (!key) return;
    pthread_mutex_lock(&_lock);
    ACLinkedNode *node = CFDictionaryGetValue(_map, (__bridge const void *)(key));
    if (node) {
        CFDictionaryRemoveValue(_map, (__bridge const void *)(node.key));
        //取出要被删除的node 频次对应的 linkList
        ACDoubleLinkedList *linkList = CFDictionaryGetValue(_freqMap, (__bridge const void *)(@(node.frequency)));
        //删除对应的node
        [linkList removeNode:node];
        if ([linkList isEmpty]) {
            //移除频次对应的 双向链表
            CFDictionaryRemoveValue(_freqMap, (__bridge const void *)(@(node.frequency)));
        }
        _totalCount --;
        _totalCost -= node.cost;
//        NSLog(@" 被删除👌🏻的数据 key:%@ value:%@ 使用频率%zd",node.key,node.value,node.frequency);
        dispatch_async(dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_LOW, 0), ^{
            [node class];
        });
    }
    pthread_mutex_unlock(&_lock);
}

- (void)removeAllObjects {
    pthread_mutex_lock(&_lock);
    [self clean];
    pthread_mutex_unlock(&_lock);
}

- (NSArray *)allkeys {
    pthread_mutex_lock(&_lock);
    CFIndex index = CFDictionaryGetCount(_map);
    const void *values[index];
    NSMutableArray *result = [@[] mutableCopy];
    CFDictionaryGetKeysAndValues(_map, NULL, values);
    CFArrayRef cfArray = CFArrayCreate(NULL, values, index, NULL);
    NSArray *results = (__bridge NSArray *)(cfArray);
    CFRelease(cfArray);
    for (ACLinkedNode *obj in results) {
        if (obj.value) {
            [result addObject:obj.key];
        }
    }
    pthread_mutex_unlock(&_lock);
    return result;
}

- (NSArray *)allValues {
    pthread_mutex_lock(&_lock);
    CFIndex index = CFDictionaryGetCount(_map);
    const void *values[index];
    NSMutableArray *result = [@[] mutableCopy];
    CFDictionaryGetKeysAndValues(_map, NULL, values);
    CFArrayRef cfArray = CFArrayCreate(NULL, values, index, NULL);
    NSArray *results = (__bridge NSArray *)(cfArray);
    CFRelease(cfArray);
    for (ACLinkedNode *obj in results) {
        if (obj.value) {
            [result addObject:obj.value];
        }
    }
    pthread_mutex_unlock(&_lock);
    return result;
}

- (NSUInteger)totalCount {
    pthread_mutex_lock(&_lock);
    NSUInteger count = _totalCount;
    pthread_mutex_unlock(&_lock);
    return count;
}

- (NSUInteger)totalCost {
    pthread_mutex_lock(&_lock);
    NSUInteger cost = _totalCost;
    pthread_mutex_unlock(&_lock);
    return cost;
}

- (void)trimToCost:(NSUInteger)costLimit  {
    BOOL finish = NO;
    pthread_mutex_lock(&_lock);
    if (costLimit == 0) {
        [self clean];
        finish = YES;
    } else if(_totalCost <= costLimit) {
        finish = YES;
    }
    pthread_mutex_unlock(&_lock);
    if (finish) return;
    
    NSMutableArray *holder = [NSMutableArray new];
    while (!finish) {
        if (pthread_mutex_trylock(&_lock) == 0) {
            if (_totalCost > costLimit) {
                ACLinkedNode *node = [self _clearMinFreqNode];
                if (node) [holder addObject:node];
            } else {
                finish = YES;
            }
            pthread_mutex_unlock(&_lock);
        } else {
            usleep(10 * 1000); //10 ms
        }
    }
    if (holder.count) {
        dispatch_async(dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_LOW, 0), ^{
            [holder count]; // release in queue
        });
    }
}

- (void)trimToCount:(NSUInteger)countLimit {
    BOOL finish = NO;
    pthread_mutex_lock(&_lock);
    if (countLimit == 0) {
        [self clean];
        finish = YES;
    } else if (_totalCount <= countLimit) {
        finish = YES;
    }
    pthread_mutex_unlock(&_lock);
    if (finish) return;
    
    NSMutableArray *holder = [NSMutableArray new];
    while (!finish) {
        if (pthread_mutex_trylock(&_lock) == 0) {
            if (_totalCount > countLimit) {
                ACLinkedNode *node = [self _clearMinFreqNode];
                if (node) [holder addObject:node];
                
            } else {
                finish = YES;
            }
            pthread_mutex_unlock(&_lock);
        } else {
            usleep(10 * 1000); //10 ms
        }
    }
    if (holder.count) {
        dispatch_async(dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_LOW, 0), ^{
            [holder count]; // release in queue
        });
    }
}

#pragma mark - private
- (void)clean {
    _totalCount = 0;
    _totalCost = 0;
    _minFreq = 1;
    
    if (CFDictionaryGetCount(_map) > 0) {
        CFMutableDictionaryRef holder = _map;
        _map = CFDictionaryCreateMutable(CFAllocatorGetDefault(), 0, &kCFTypeDictionaryKeyCallBacks, &kCFTypeDictionaryValueCallBacks);
        dispatch_async(dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_LOW, 0), ^{
            CFRelease(holder); // hold and release in specified queue
        });
    }
    
    if (CFDictionaryGetCount(_freqMap) > 0) {
        CFMutableDictionaryRef holder = _freqMap;
        _freqMap = CFDictionaryCreateMutable(CFAllocatorGetDefault(), 0, &kCFTypeDictionaryKeyCallBacks, &kCFTypeDictionaryValueCallBacks);
        dispatch_async(dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_LOW, 0), ^{
            CFRelease(holder); // hold and release in specified queue
        });
    }
}

#pragma mark - Freq++
- (void)freqPlus:(ACLinkedNode *)node {
    NSUInteger frequency = node.frequency;
    ACDoubleLinkedList *oldLinkList = CFDictionaryGetValue(_freqMap, (__bridge const void*)(@(node.frequency)));
    [oldLinkList removeNode:node];
    if ([oldLinkList isEmpty]) {
        //移除旧的的链表
        CFDictionaryRemoveValue(_freqMap, (__bridge const void *)(@(node.frequency)));
    }
    if (_minFreq == frequency && ([oldLinkList isEmpty] || oldLinkList == nil)) {
        _minFreq++;
    }
    frequency ++;
    node.frequency ++;
    ACDoubleLinkedList *newLinkList =  CFDictionaryGetValue(_freqMap, (__bridge const void*)(@(node.frequency)));
    if (newLinkList == nil) {
        newLinkList = [[ACDoubleLinkedList alloc] init];
        CFDictionarySetValue(_freqMap, (__bridge const void *)(@(frequency)), (__bridge const void *)(newLinkList));
    }
    [newLinkList insertNodeAtHead:node];
}

#pragma mark - Eliminate MinFreqNode
- (void)eliminate:(NSUInteger)cost {
    if (_totalCount < _countLimit && _totalCost + cost < _costLimit)  {
        return;
    }
    ACLinkedNode *node = [self _clearMinFreqNode];
    dispatch_async(dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_LOW, 0), ^{
        [node class];
    });
}

- (ACLinkedNode *)_clearMinFreqNode {
    ACDoubleLinkedList *linkList = CFDictionaryGetValue(_freqMap, (__bridge const void*)(@(_minFreq)));
    ACLinkedNode *node = linkList.tail;
    [linkList removeNode:node];
    if ([linkList isEmpty]) {
        CFDictionaryRemoveValue(_freqMap, (__bridge const void *)(@(_minFreq)));
    }
    CFDictionaryRemoveValue(_map, (__bridge const void *)(node.key));
    _totalCount --;
    _totalCost -= node.cost;
//    NSLog(@" 被淘汰的数据 key:%@ value:%@ 使用频率%zd",node.key,node.value,node.frequency);
    return node;
}

- (void)dealloc {
    CFRelease(_map);
    CFRelease(_freqMap);
#if DEBUG
    NSLog(@"%s",__func__);
#endif
}

@end
